package exam.test;

import java.util.ArrayList;
import java.util.List;

public class TwoSum {

    public static int[] findTwoSum(int[] list, int sum) {
        if (list == null || list.length <= 1) {
            return null;
        }
        QuickSort(list, 0, list.length - 1);
        List<Integer> retList = new ArrayList<>();
        for (int i = 0; i <list.length; i++) {
            int value = list[i];
            if (sum - value < value) {
                break;
            } else {
                int index = find(list, sum - value, i + 1, list.length - 1);
                if (index >= 0) {
                    retList.add(value);
                    retList.add(list[index]);
                }
            }
        }

        int[] ints = null;
        if (retList.size() > 0) {
            ints = new int[retList.size()];
            for (int i = 0; i < retList.size(); i++) {
                ints[i] = retList.get(i);
            }
        }

        return ints;
    }

    private static int find(int[] nums, int num, int start, int end) {
        if (start > end) {
            return -1;
        }
        int mid = (start + end) / 2;
        if (nums[mid] == num) {
            return mid;
        } else if (nums[mid] < num) {
            return find(nums, num, mid + 1, end);
        } else {
            return find(nums, num, start, mid - 1);
        }
    }

    private static void QuickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int key = nums[left];
        int i = left;
        int j = right;
        while (i < j) {
            while (nums[j] >= key && i < j) {
                j--;
            }
            while (nums[i] <= key && i < j) {
                i++;
            }
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        nums[left] = nums[i]; 
        nums[i] = key;
        QuickSort(nums, left, i - 1);
        QuickSort(nums, i + 1, right);
    }

    public static void main(String[] args) {
        int[] indices = findTwoSum(new int[]{3, 1, 5, 7, 5, 9}, 10);
        if (indices != null) {
            System.out.println(indices[0] + " " + indices[1]);
        }
    }
}
